package jianzhi_offer;

/**
 * @author: zhouyang
 * @descrpition:
 * @time: 2019-04-17 13:44
 */
public class _65_机器人的运动范围 {
    int res = 0;
    public int movingCount(int threshold, int rows, int cols)
    {
        if(rows == 0 || cols == 0) return 0;
        boolean [][]dp = new boolean[rows][cols];
        dfs(0,0,rows,cols,threshold,dp);
        return this.res;
    }

    public void dfs(int x,int y,int rows,int cols,int threshold,boolean [][]dp){
        if(!judge(x,y,threshold)) return ;
        this.res ++;
        dp[x][y] = true;
        if(x != 0 && !dp[x-1][y]) dfs(x-1,y,rows,cols,threshold,dp);
        if(y != 0 && !dp[x][y-1]) dfs(x,y-1,rows,cols,threshold,dp);
        if(x != rows-1 && !dp[x+1][y]) dfs(x+1,y,rows,cols,threshold,dp);
        if(y != cols-1 && !dp[x][y+1]) dfs(x,y+1,rows,cols,threshold,dp);
    }

    public boolean judge(int x,int y,int threshold){
        int res = 0;
        while(x > 0){
            res += x%10;
            x /= 10;
        }
        while(y > 0){
            res += y%10;
            y /= 10;
        }
        return res <= threshold;
    }
}
